package main

func main()  {
	
}

type lianNode struct {
	val int
	next *lianNode
	random *lianNode
}

func copylianbiao(head *lianNode) *lianNode {

	if head == nil {
		return nil
	}

	// 复制 A B C =》AA' BB' CC'
	cur := head
	for cur != nil {
		cur.next = &lianNode{
			val:    cur.val,
			next:   cur.next,
		}
		cur = cur.next.next
	}

	// 复制random
	cur = head
	for cur != nil {
		cur.next.random = cur.random.next
		cur = cur.next.next
	}

	cur = head
	ret := head.next
	for cur != nil {
		c1 := cur.next
		cur.next = c1.next
		if c1.next != nil {
		c1.next = cur.next.next
		}
		cur = cur.next
	}
	return  ret
}
